package main

import (
	"fmt"
)

func main() {
	// 值传递
	//var array = [3]int{0, 1, 2}
	//var array2 = array
	//array2[2] = 5
	//fmt.Println(array, array2)

	// 引用传递，这里创建的是一个切片而非一个数组
	var nums = []int{2, 1, 7, 9, 5, 8}
	//b := make([]int, len(nums), )
	//copy(b, nums)
	//b[0] = 1

	//var nums = [...]int{2, 1, 7, 9, 5, 8}
	sort(nums, 0, len(nums)-1)
	fmt.Println(nums)
}

func sort(A []int, lo int, hi int) {
	if lo >= hi {
		return
	}

	mid := lo + (hi-lo)/2

	sort(A, lo, mid)
	sort(A, mid+1, hi)

	merge(A, lo, mid, hi)
}

func merge(nums []int, lo int, mid int, hi int) {
	copies := make([]int, len(nums))
	copy(copies, nums)

	k := lo
	i := lo
	j := mid + 1

	for k <= hi {

		if i > mid {
			nums[k] = copies[j]
			k++
			j++
		} else if j > hi {
			nums[k] = copies[i]
			k++
			i++
		} else if copies[j] < copies[i] {
			nums[k] = copies[j]
			k++
			j++
		} else {
			nums[k] = copies[i]
			k++
			i++
		}

	}
}
